package leetcode.day_2021_3_1_2022_3_7;

/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class LeetCode0042 {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

    public static int trap(int[] height) {
        int n = height.length-1;;
        int left = 0, right = n;
        int lmax = height[left], rmax = height[right];
        int sum = 0;
        while (left <= right) {
            lmax = Math.max(lmax, height[left]);
            rmax = Math.max(rmax, height[right]);

            if (lmax < rmax) {
                sum += (lmax-height[left]);
                left++;
            } else {
                sum += (rmax-height[right]);
                right--;
            }
        }
        return sum;
    }
}
